{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "DzJ8FQ_HsP7Q"
      },
      "source": [
        "# Distributed SDCA\n",
        "\n",
        "$\\def\\a{\\alpha} \\def\\d{\\Delta\\a} \\def\\l{\\ell} \\def\\P{\\mathcal{P}}$\n",
        "We want to minimize on $K$ machines the following objective\n",
        "\n",
        "$$ P(w) = \\frac{1}{n}\\sum_{i=1}^n \\l_i(x_i^T w)+\\lambda g(w) $$\n",
        "\n",
        "By Fenchel duality, this is equivalent to maximizing its dual\n",
        "\n",
        "$$ D(\\a) = \\frac{1}{n} \\left(\\sum_{i=1}^n -\\l_i^\\star(-\\a_i)\\right) -\\lambda g^\\star\\left(\\tfrac{1}{\\lambda n} X\\a\\right) $$\n",
        "\n",
        "which can be done very efficiently on a single machine with SDCA [3].\n",
        "\n",
        "Here $f^\\star$ denotes the convex dual of a convex function $f$, $\\l_i$ is the loss for the example $i$, $n$ is the total number of examples and $\\lambda n$ is the L2 parameter.\n",
        "\n",
        "Following [1,2], we use a data partition $\\P_1,\\dots,\\P_K$ of $\\{1,2,\\dots,n\\}$ such that $\\P_k$ contains the examples on machine $k$.\n",
        "For an $n$-dimensional vector $h$, we denote by $h_{[k]}$ the $n$-dimensional vector restricted to the machine $k$: $(h_{[k]})_i = h_i$ if $i\\in\\P_k$ and $0$ otherwise.\n",
        "\n",
        "## CoCoA+ Local Solver\n",
        "\n",
        "The local subproblem on machine $k$ is [1, 2]\n",
        "\n",
        "$$ \\max_{\\d_{[k]}} \\mathcal{G}^{\\sigma}_k (\\d_{[k]}) $$\n",
        "\n",
        "with\n",
        "\n",
        "$$\n",
        "\\mathcal{G}^{\\sigma}_k (\\d_{[k]}) =\n",
        "-\\frac{1}{n} \\sum_{i\\in\\P_k}\\l_i^\\star(-\\a_i-(\\d_{[k]})_i) -\\frac{1}{n} w^T X\n",
        "\\d_{[k]}- \\frac{\\lambda}{2}\\sigma \\left\\| \\frac{1}{\\lambda n} X \\d_{[k]}\n",
        "\\right\\|^2 $$\n",
        "\n",
        "$\\sigma$ is a parameter the measures the difficulty of the data partition. CoCoA+ makes the choice $ \\sigma = K $\n",
        "\n",
        "This decision is motivated in [2] and shown to be more efficient than the previous CoCoA choice ($\\sigma = 1$).\n",
        "\n",
        "For one example, the problem is simply\n",
        "\n",
        "$$ \\max_{\\d} \\left\\{ D_i(\\d) = -\\l_i^\\star(-(\\a_i+\\d)) - \\bar{y}_i \\d - \\frac{A}{2} \\d^2 \\right\\} $$\n",
        "\n",
        "where we have defined $A=\\sigma X_i^2/(\\lambda n)$ and $ \\bar{y}_i = w^T X_i$\n",
        "\n",
        "To take into account example weights, it suffices to replace $1/n$ by $s_i/S$ where $s_i$ is the weight of the i-th example and $S=\\sum s_i$. For our problem, this will only change $A$ to $\\sigma X_i^2s_i/(\\lambda S)$.\n",
        "\n",
        "### Hinge Loss\n",
        "\n",
        "Hinge loss is given by $ \\l_i(u) = \\max(0,1-y u) $. Its convex dual is $\\l_i^\\star(-a) = -a y$ with the constraint $ a y\\in [0,1] $.\n",
        "\n",
        "The solution for the update is given explicitly in [3]. To derive the CoCoA+ formulation, we replace $\\lambda$ by $\\frac{\\lambda}{\\sigma}$. This gives\n",
        "\n",
        "$$ \\d = \\frac{y - \\bar{y}}{A} $$\n",
        "\n",
        "with the restriction that $y(\\a+\\d)\\in(0,1)$.\n",
        "\n",
        "### Smooth Hinge Loss\n",
        "\n",
        "Smooth hinge loss is given by\n",
        "\n",
        "$$ \\l_i(u) =\n",
        "\\begin{cases}\n",
        "0 \\:\\:\\: \u0026 y_i u \\geq 1\\\\\n",
        "1-y_i u -\\gamma/2 \\:\\:\\:\u0026 y_i u \\leq1-\\gamma \\\\\n",
        "\\frac{(1-y_i u)^2}{2\\gamma} \u0026 \\text{otherwise}\n",
        "\\end{cases} $$\n",
        "\n",
        "The optimal $\\d$ is computed to be\n",
        "\n",
        "$$\\d = \\frac{y-\\bar{y}-\\gamma\\a}{A+\\gamma} $$\n",
        "\n",
        "with the restriction that $y(\\a+\\d)\\in(0,1)$. We see that we recover standard hinge update for $\\gamma = 0$. The details of the computation can be found in Appendix.\n",
        "\n",
        "### Squared Loss\n",
        "\n",
        "Squared loss is $ \\l_i(u) = \\frac{1}{2}(u-y)^2 $ with dual $ \\l_i^\\star(v) =\\frac{1}{2}v^2+y v$.\n",
        "\n",
        "The closed form solution for squared loss is given in [4]. By replacing again $\\lambda$ by $\\frac{\\lambda}{\\sigma}$ we obtain\n",
        "\n",
        "$$ \\d = -\\frac{\\a + w^T X_i - y}{1 + \\frac{\\sigma X_i^2}{2 \\lambda n}} $$\n",
        "\n",
        "### Logistic loss\n",
        "\n",
        "Logistic loss is $ \\l_i(u) = \\log (1+e^{-uy_i}) $ and its dual is\n",
        "\n",
        "$$ \\l_i^\\star(v) = -vy_i\\log(-vy_i) + (1+vy_i)\n",
        "\\log(1+vy_i) $$\n",
        "\n",
        "The label $y_i$ is $\\pm 1$ and the dual loss is only defined for $ -y_i v\\in (0,1) $. We then have the constraint\n",
        "\n",
        "$$  y_i (\\a+\\d) \\in (0,1) $$\n",
        "\n",
        "The problem of finding the maximum of $ D(\\d) $ can be reformulated as the problem of finding the unique zero of its derivative. Newton method works well for finding the zero of $ D'(\\d) $ but can be a bit unstable due to the constraint requiring $y_i(\\a+\\d)$ be in the range $(0,1)$ (more on this below).\n",
        "\n",
        "To avoid this problem, we make the following change of variable\n",
        "\n",
        "$$ y(\\a+\\d) = \\frac{1}{2}(1+\\tanh x) $$\n",
        "\n",
        "This enforces the constraint and is well suited because the objective derivative\n",
        "has the following simple form:\n",
        "\n",
        "$$ D' = H(x) = -2y x - \\bar{y} + A\\a -\\frac{A}{2y}(1+\\tanh x) $$\n",
        "\n",
        "with derivative\n",
        "\n",
        "$$ H'(x) = -2y - \\frac{A}{2y}(1-\\tanh^2 x) $$\n",
        "\n",
        "This function is always positive or always negative so that $H$ is strictly monotonic.\n",
        "\n",
        "We can start Newton algorithm at $x_0=0$ which corresponds to $ y(\\a+\\d) = 0.5 $. A Newton step is given by\n",
        "\n",
        "$$x_{k+1} = x_k - \\frac{H(x_k)}{H'(x_k)} $$\n",
        "\n",
        "The convergence is very fast with the modified function and 5 Newton steps should be largely enough.\n",
        "\n",
        "#### Proof of convergence\n",
        "\n",
        "The second derivative of $H$\n",
        "\n",
        "$$ H''(x) = \\frac{A}{y} \\tanh x (1-\\tanh^2 x) $$\n",
        "\n",
        "is bounded and quadratic convergence should be guaranteed if we are close enough to the solution (see proof [here](https://en.wikipedia.org/wiki/Newton%27s_method#Proof_of_quadratic_convergence_for_Newton.27s_iterative_method)).\n",
        "\n",
        "However we can't really know if we are close to the zero. To prove the convergence in any cases, we can use Kantovitch Theorem (reviewed in [5]). The sufficient condition to have convergence is that we start at a point $ x_0 $ such that\n",
        "\n",
        "$$\n",
        "\\left|\\frac{4A H(x_0)}{H'(x_0)^2} \\right|\\leq 1\n",
        "$$\n",
        "\n",
        "If $ A$ is not small, the starting point $x_0 = 0$ doesn't satisfy this condition and we may solve the above inequality to find a starting point which does.\n",
        "\n",
        "However, in practice, convergence with $x_0 = 0$ always happens (tested for a sample of generic values for the parameters).\n",
        "\n",
        "### Poisson log loss\n",
        "\n",
        "Poisson log loss is defined as $ \\l(u) = e^u - uy $ for label $y \\geq 0.$ Its dual is\n",
        "\n",
        "$$ \\l^\\star(v) = (y+v) (\\log(y+v) - 1) $$\n",
        "\n",
        "and is only defined for $ y+v \u003e 0 $. We then have the constraint\n",
        "\n",
        "$$  y \u003e \\a+\\d. $$\n",
        "\n",
        "The dual is\n",
        "\n",
        "$$ D(\\d) = -(y-\\a-\\d) (\\log(y-\\a-\\d) - 1) - \\bar{y} \\d - \\frac{A}{2} \\d^2 $$\n",
        "\n",
        "and its derivative is,\n",
        "\n",
        "$$ D'(\\d) = \\log(y-\\a-\\d) - \\bar{y} - A\\d $$\n",
        "\n",
        "Similar to the logistic loss, we perform a change of variable to handle the constraint on $ \\d $\n",
        "\n",
        "$$ y - (\\a+\\d) = e^x $$\n",
        "\n",
        "After this change of variable, the goal is to find the zero of this function\n",
        "\n",
        "$$ H(x) = x - \\bar{y} -A(y-\\a-e^x) $$\n",
        "\n",
        "whose first derivative is\n",
        "\n",
        "$$ H'(x) = 1+Ae^x $$\n",
        "\n",
        "Since this function is always positive, $H$ is increasing and has a unique zero.\n",
        "\n",
        "We can start Newton algorithm at $\\d=0$ which corresponds to $ x =\\log(y-\\a)$. As before the Newton step is given by\n",
        "\n",
        "$$x_{k+1} = x_k - \\frac{H(x_k)}{H'(x_k)}. $$\n",
        "\n",
        "### References\n",
        "\n",
        "[1] C. Ma et al., [Adding vs. Averaging in Distributed Primal-Dual Optimization](https://arxiv.org/pdf/1502.03508.pdf), 2015.\n",
        "\n",
        "[2] C. Ma et al., [Distributed Optimization with Arbitrary Local Solvers](https://arxiv.org/pdf/1512.04039.pdf), 2015.\n",
        "\n",
        "[3] S. Shalev-Shwartz, T. Zhang, [Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization](http://www.jmlr.org/papers/volume14/shalev-shwartz13a/shalev-shwartz13a.pdf), 2013.\n",
        "\n",
        "[4] S. Shalev-Shwartz, T. Zhang, [Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization](https://arxiv.org/pdf/1309.2375.pdf), 2013.\n",
        "\n",
        "[5] A. Galantai, [The theory of Newton’s method](https://www.sciencedirect.com/science/article/pii/S0377042700004350), 2000.\n",
        "\n",
        "## Appendix\n",
        "\n",
        "#### Dual computation for smooth hinge loss\n",
        "\n",
        "We want to compute $\\l^\\star(v) = \\max_u [ uv-\\l(u) ] $ where $\\l$ is smooth hinge loss. We thus have to solve $v=\\l'(u)$. The derivative of smooth hinge loss is given by\n",
        "\n",
        "$$ \\l'(u) =\n",
        "\\begin{cases}\n",
        "0 \\:\\:\\: \u0026 y_i u \\geq 1\\\\\n",
        "-y \\:\\:\\:\u0026 y_i u \\leq1-\\gamma \\\\\n",
        "\\frac{u-y}{\\gamma} \u0026 \\text{otherwise}\n",
        "\\end{cases} $$\n",
        "\n",
        "By solving for $v$, we find the dual of smooth hinge loss as\n",
        "\n",
        "$$ \\l^\\star(v) = yv + \\frac{\\gamma}{2}v^2 $$\n",
        "\n",
        "with the restriction $ yv \\in (0,1) $.\n",
        "\n",
        "Now, we can now minimize the dual objective with respect to $\\d$\n",
        "\n",
        "$$ D(\\a+\\d) = -\\l^\\star(-\\a-\\d)-\\bar{y}\\d-\\frac{A}{2} \\d^2 $$\n",
        "\n",
        "which gives the expected result\n",
        "\n",
        "$$\\d = \\frac{y-\\bar{y}-\\gamma\\a}{A+\\gamma} $$\n",
        "\n",
        "with the constraint $ y(\\a+\\d) \\in (0,1)$."
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "SDCA.ipynb",
      "provenance": [
        {
          "file_id": "1dYYnnjfGC6CIpfwy__EXL81Xnl26wiKM",
          "timestamp": 1539909050558
        }
      ],
      "version": "0.3.2"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
